import random
import time

# 冒泡
alist = [2,4,10,22,3,4,66,20,1,0]
ln =  len(alist)
for i in range(ln-1):
    for j in range(ln-1-i):
        if alist[j] > alist[j+1]:
            alist[j],alist[j+1] =  alist[j+1],alist[j]

print(alist)

###
alist = [2,4,10,22,3,4,66,20,1,0]
ln =  len(alist)
for i in range(1,ln-1):
    for j in range(ln-i):
        if alist[j] > alist[j+1]:
            alist[j],alist[j+1] =  alist[j+1],alist[j]

print(">>>>",alist)


###
# 选择排序
a = [1,6,21,3,5]
def selectSort(list):
    for i in range(len(list)-1):
        min_list = i
        for j in range(i+1, len(list)):
            if list[j] < list[min_list]:
                min_list = j
        list[min_list],list[i] = list[i],list[min_list]
        print(list)
    return list

print(selectSort((a)))


# 插入排序
def insertion_sort(arr):
    # 第一层for表示循环插入的编数
    for i in range(1,len(arr)):
        # 当前需要插入的元素
        current = arr[i]
        # 与当前元素比较的比较元素
        pre_index = i - 1
        while pre_index >= 0 and arr [pre_index] > current:
            # 当比较元素大于当前元素则把比较元素后移
            arr[pre_index + 1] = arr[pre_index]
            # 往前选择下一个比较元素
            pre_index -= 1
        # 当比较元素小于当前元素，则当前元素插入在其后面
        arr[pre_index + 1] = current
    return arr

A = [11,99,33,69,77,88,55,11,33,36,22,12,31,45]
B = insertion_sort(A)
print("插入排序》》》",B)


# 快速排序
def quickSort(alist):
    if not alist:
        return alist
    pivot = random.choice(alist)
    print(pivot)
    equalList = []
    smallerList = []
    biggerList = []
    for item in alist:
        if item < pivot:
            smallerList.append(item)
        elif item == pivot:
            equalList.append(item)
        else:
            biggerList.append(item)
    return quickSort(biggerList) + equalList + quickSort(smallerList)

a = [3,1,2,8,7,0,3]

su = quickSort(a)
print(">>>快速排序",su)

# 希尔排序
def shell_sort(arr):
    # 取整计算增量（间隔）值
    gap = len(arr)//2
    while gap > 0:
        # 从增量值开始遍历比较
        for i in range(gap,len(arr)):
            j = i
            current = arr[i]
            # 元素与他同列的前面的每个元素比较，如果比前面的小则互换，其实就是插入排序
            while j - gap >=0 and current < arr[j - gap]:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = current
        # 缩小增量（间隔）值
        gap //=2
    return arr
sorted_arr = shell_sort([3,1,8,9,2,6,0,8])
print("希尔排序》》》",sorted_arr)

# 归并排序
def merge_sort(lst):
    #递归结束条件
    if len(lst) <=1:
        return lst

    # 分解问题，并递归调用
    middle = len(lst)//2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])

    # 合并左右半部分，完成排序
    merged_lst = []
    while left and right:
        if left[0] <= right[0]:
            merged_lst.append(left.pop(0))
        else:
            merged_lst.append(right.pop(0))

    # 如果左部分或者右部分有剩余，那就拼接到已排好的序列中
    merged_lst.extend(right if right else  left)
    return merged_lst

A = [11,99,33,69,77,88,55,11,32,33,12,35,66,20]
B = merge_sort(A)
print("归并排序》》》",B)


# 记数排序
def couting_sort(array):
    largest = max(array); smallest = min(array) #获取最大，最小值
    counter = [0 for i in range(largest-smallest+1)] #用于统计个数的空数组
    idx = 0 #桶内索引值
    for i in range(len(array)):
        counter[array[i]-smallest] += 1 #统计每个元素出现的次数
    for j in range(len(counter)):
        while counter[j] > 0:
            array[idx] = j + smallest #取出元素
            idx += 1
            counter[j] -= 1
    return array

A = [5,2,8,9,1,2]
couting_sort(A)
print(">>>>计数排序",A)
